/**
 * Copyright 2007 Igor Chaves Cananéa
 *
 * This file is part of PBSFW
 *
 * PBSFW is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2 of the License.
 *
 * PBSFW is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef _HEAP_IMPLEMENTATION_H_
#define _HEAP_IMPLEMENTATION_H_

#include "task.h"
#include "process.h"

namespace pbsfw {
	/**
	* This class implements an array-based heap that is used by the scheduler
	* to schedule Task objects for the simulator. It can replace of the
	* std::map based scheduler if long-running simulations were many tasks are
	* created are the norm.
	*
	* Performance tests showed that the std::map based scheduler is faster than
	* the heap implementation when the number of scheduled tasks is under
	* 10.000 tasks. Otherwise, the heap scheduler is faster and becomes faster
	* with the increase on the number of tasks.
	*/
	class Heap {
		private:
			Task **heap;
			uint currentMax;
			uint last;

			/**
			 * Operations used to maintain the heap
			 */
			inline void upheap();
			inline void downheap();

			/**
			 * Called when there is no more space in the heap. Doubles the
			 * memory available and copies all taks to the new heap. Due to
			 * the natural object life-cycle of discrete-event simulations, the
			 * memory allocation will eventually stabilize and no longer will
			 * this method be called.
			 */
			inline void reallocate();

			/**
			 * Left child position in the heap
			 */
			uint left(uint i) const {
				return (i << 1) + 1;
			}

			/**
			 * Right child position in the heap
			 */
			uint right(uint i) const {
				return (i << 1) + 2;
			}

			/**
			 * The position of a parent in the heap
			 */
			uint parent(uint i) const {
				return i & 0x01 ? (i - 1) >> 1 : (i - 2) >> 1;
			}

			/**
			 * Checks if a heap position has a child. This can be done by
			 * checking if the position has a left child and that the child
			 * position is not empty.
			 */
			bool hasChild(uint i) const {
				uint leftChild = this->left(i);
				return leftChild < this->last && this->heap[leftChild] != 0;
			}

			/**
			 * Checks if a position has a parent. Every position has a parent,
			 * except for the first position in the heap. This method is only
			 * called on existing tasks, so I don't have to check if the
			 * position is empty
			 */
			bool hasParent(uint i) const {
				return i != 0;
			}

			/**
			 * Determines which task has the highest priority, which in this
			 * case is the task that has the smalles scheduled time.
			 */
			uint smallest(uint i, uint j) const {
				Task *iTask = this->heap[i];
				Task *jTask = this->heap[j];

				/**
				 * The following works, because it doesn't matter if both task
				 * positions are empty.
				 */
				if (jTask == 0) {
					return i;
				}
				if (iTask == 0) {
					return j;
				}

				// Effectively verifies who has the highest priority
				if (iTask->getTime() < jTask->getTime()) {
					return i;
				}
				return j;
			}

			/**
			 * Swaps two tasks in the heap
			 */
			void swap(uint from, uint to) {
				Task *t = this->heap[from];
				this->heap[from] = this->heap[to];
				this->heap[to] = t;
			}

		public:
			/**
			 * Initilizes the heap with 1024 legal positions and sets each
			 * position to NULL (0).
			 */
			Heap(uint currentMax = 1024)
				: heap(0), currentMax(currentMax), last(0) {
				this->heap = new Task*[this->currentMax];
				for (uint i = 0; i < this->currentMax; ++i) {
					this->heap[i] = 0;
				}
			}

			~Heap() {
				delete [] this->heap;
			}

			/**
			 * Checks if the heap is empty. This is done by check if the first
			 * position is NULL (0).
			 */
			bool empty() const {
				return this->heap[0] == 0;
			}

			/**
			 * Removes the next scheduled task from the heap and determines the
			 * next task to be removed.
			 */
			Task *remove() {
				if (this->last > 0) {
					--this->last;

					Task *t = this->heap[0];
					this->heap[0] = this->heap[this->last];
					this->heap[this->last] = 0;

					this->downheap();

					return t;
				}
				return 0;
			}

			/**
			 * Inserts a new task to be scheduled in the heap and then finds
			 * it position according to its priorty (scheduled time).
			 */
			void insert(Task *t) {
				if (this->last == this->currentMax) {
					this->reallocate();
				}
				this->heap[this->last] = t;
				this->upheap();
				++this->last;
			}

			/**
			 * Called by the scheduler to reset the Tasks on the heap.
			 */
			void reset();
	};

	/**
	 * Called when a task was insert in the heap. Puts the last task inserted at
	 * its correct position, according to its priority (scheduled time).
	 */
	inline void Heap::upheap() {
		uint current = this->last;

		while (this->hasParent(current)) {
			uint father = this->parent(current);

			/**
			 * Deterimne the smallest (higher priority). Only need to check the
			 * father. If the father has a higher priority, stop hear.
			 */
			uint small = this->smallest(father, current);
			if (small == father) {
				break;
			}

			// Otherwise, swap father and child and continue the algorithm.
			this->swap(father, current);
			current = father;
		}
	}

	/**
	 * Called when a task was removed from the heap. Puts the task on the top
	 * at its correct position, according to its priority (scheduled time)
	 */
	inline void Heap::downheap() {
		uint current = 0;

		while (this->hasChild(current)) {
			// Determine the smallest (higher priority) child.
			uint small = this->smallest(this->left(current), this->right(current));

			// If the current task is the smallest, then we stop.
			small = this->smallest(current, small);
			if (small == current) {
				break;
			}

			// Otherwise, swap them and restart the repositioning.
			this->swap(current, small);
			current = small;
		}
	}

	/**
	 * Called when there is no more space in the heap. Doubles the
	 * memory available and copies all taks to the new heap.
	 */
	inline void Heap::reallocate() {
		uint nextMax = this->currentMax << 1;
		Task **temp = new Task*[nextMax];

		/**
		 * Copies the tasks to the new heap and also sets the remaining
		 * new positions to NULL (0)
		 */
		for (uint i = 0; i < this->currentMax; ++i) {
			temp[i] = this->heap[i];
			temp[i + this->currentMax] = 0;
		}

		delete [] this->heap;
		this->heap = temp;
		this->currentMax = nextMax;
	}

};

#endif
